/*
 * @lc app=leetcode.cn id=45 lang=cpp
 *
 * [45] 跳跃游戏 II
 */

// @lc code=start
class Solution
{
private:
    unsigned int g_step = -1;

public:
    int jump(vector<int> &nums)
    {
        int n = nums.size();
        if(n == 1)
            return 0;
        int l = 0, r = 0;
        int step = 0;
        while(r < n - 1)
        {
            step++;
            int max_r = r;
            for(int i = l; i <= r; i++)
            {
                if(i + nums[i] > max_r)
                    max_r = i + nums[i];//[l,r]区间内下一跳能到达的最远距离
            }
            l = r + 1;
            r = max_r;
            //此时[l, r]就是下一跳所有能到达的区间
        }
        return step;
    }

};
// @lc code=end
